package offer.offer03;

/**
 * 100, 63 两个链表相交之后就不分开了, 可以先数数两个链表的长度, 找到二者同样长度的一截, 然后逐个比较;
 */
public class Solution52 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int aLen = 0, bLen = 0;
        ListNode aPointer = headA, bPointer = headB;

        while (aPointer != null){
            aPointer = aPointer.next;
            aLen ++;
        }
        while (bPointer != null){
            bPointer = bPointer.next;
            bLen ++;
        }
        aPointer = headA;
        bPointer = headB;
        if(aLen > bLen){
            for(int i = 0; i < aLen - bLen; i++)
                aPointer = aPointer.next;
        }else {
            for(int i = 0; i < bLen - aLen; i++)
                bPointer = bPointer.next;
        }
        while (aPointer != null){
            if(aPointer == bPointer)
                return aPointer;
            aPointer = aPointer.next;
            bPointer = bPointer.next;
        }

        return null;
    }
    //两指针遍历俩个链表，长度不同时, 第二轮遍历的时候会进行匹配。若长度相同，则第一次进行匹配。
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode node1=headA;
        ListNode node2=headB;
        while (node1!=node2){
            node1=(node1==null)?headB:node1.next;
            node2=(node2==null)?headA:node2.next;
        }
        return node1;
    }

}


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}